---
id: 栈和队列
title: 栈和队列
---


#### 物理结构和逻辑结构  
常用的数据结构有很多，但大多数都以数组或链表作为存储方式，数组和链表可以被看作数据存储的物理结构。  
逻辑结构是抽象的概念，它依赖于物理结构而存在。  

物理结构有顺序存储结构和链式存储结构，比如数组和链表。  
逻辑结构由线性结构和非线性结构。  
线性结构有顺序表、栈、队列等。 非线性结构，树。


## 栈(stack)
栈是一种线性数据结构，栈中的元素只能先入后出(First In Last Out，简称FILO)。最早进入的元素存放的位置叫作栈底(bottom)，最后进入的元素存放的位置叫作栈顶 (top)。  

#### 栈的应用  
栈的输出顺序和输入顺序相反，所以栈通常用于对“历史”的回溯，也就是逆流而上追溯“历史”。
  例如实现递归的逻辑，就可以用栈来代替，因为栈可以回溯方法的调用链。  

  栈还有一个著名的应用场景是面包屑导航，使用户在浏览页面时可以轻松地回
溯到上一级或更上一级页面。

## 队列(queue)
队列(queue)是一种线性数据结构，可以把它想象成排队的场景。 不同于栈的先入后出，队列中的元素只能先入先出(First In First Out，简称 FIFO)。队列的出口端叫作队头(front)，队列的入口端叫作队尾(rear)。
### 实现队列 

- python
```python

# 采 用 List 来 容 纳 Queue的数据项
# 将List首端作为队列 尾端
# List的末端作为队列 首端
# enqueue()复杂度为 O(n)
# dequeue()复杂度为 O(1)

class Queue:
    def __init__(self):
        self.item = []

    def isEmpty(self):
        return self.item == []

    def enqueue(self, item):
        self.item.insert(0, item)

    def dequeue(self):
        return self.item.pop()

    def size(self):
        return len(self.item)

q = Queue();
print(q.isEmpty())
print(q.enqueue(3))
print(q.enqueue(4))
print(q.size())
print(q.dequeue())
print(q.size())

```
#### 队列的应用
队列的输出顺序和输入顺序相同，所以队列通常用于对“历史”的回放，也就是按照“历史”顺序，把“历史”重演一遍。  
例如在多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列中的次序的。  
再如网络爬虫实现网站抓取时，也是把待抓取的网站URL存入队列中，再按照存 入队列的顺序来依次抓取和解析的。

- 热土豆问题（约瑟夫问题） python
```python
# 传烫手的热土豆，鼓声停的时候，手里有 土豆的小孩就要出列


class Queue:
    def __init__(self):
        self.item = []

    def isEmpty(self):
        return self.item == []

    def enqueue(self, item):
        self.item.insert(0, item)

    def dequeue(self):
        return self.item.pop()

    def size(self):
        return len(self.item)
# 算法
# 模拟程序采用队列来存放所有参加游戏的人名， 按照传递土豆方向从队首排到队尾。
# 游戏时，队首始终是持有土豆的人
# 模拟游戏开始，只需要将队首的人出队，随即再 到队尾入队，算是土豆的一次传递。
# 传递了num次后，将队首的人移除，不再入队 如此反复，直到队列中剩余1人

def hotPotato(nameList, num):
    simqueue = Queue()
    for name in nameList:
        simqueue.enqueue(name) # 加入队列

    while simqueue.size() > 1:
        for i in range(num):
            if i == num-1:
                simqueue.dequeue()
                break
            dequeue = simqueue.dequeue()
            simqueue.enqueue(dequeue)

    return simqueue.dequeue()

print(hotPotato(['轩', '张', '刘', '蒋','顾','梁','宋','王'], 3))

```

## 双端队列
那么有没有办法把栈和队列的特点结合起来，既可以先入先出，也可以先入后出呢?还真有，这种数据结构叫作双端队列(deque)。


##  优先队列(非线性)

还有一种队列，它遵循的不是先入先出，而是谁的优先级最高，谁先出队。
优先队列已经不属于线性数据结构的范畴了，它是基于二叉堆来实现的。关于
优先队列的原理和使用情况，我们会在下一章进行详细介绍。

## 栈和队列的代码实现
### 实现栈

### 实现双端队列
### 实现优先队列